Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

For example,

Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

Solution:

  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode(int x) {
  7.  *         val = x;
  8.  *         next = null;
  9.  *     }
  10.  * }
  11.  */
  12. public class Solution {
  13.   public ListNode swapPairs(ListNode head) {
  14.     // Base Case: The list is empty or has only one node
  15.     if (head == null || head.next == null)
  16.       return head;
  18.     // Store head of list after two nodes
  19.     ListNode rest = head.next.next;
  21.     // Change head
  22.     ListNode newhead = head.next;
  24.     // Change next of second node
  25.     head.next.next = head;
  27.     // Recur for remaining list and change next of head
  28.     head.next = swapPairs(rest);
  30.     // Return new head of modified list
  31.     return newhead;
  32.   }
  33. }